1. Field of the Invention
The present invention relates to a quality of service (QoS) queuing system and a method for queuing clients (packets) in a manner that eliminates the reordering of the clients even after a QoS class of one of the clients is altered (promoted/demoted).
2. Description of Related Art
Mechanisms that provide various levels of QoS use schedulers and queues to offer privileged treatment or services to clients (jobs) that request those services. Clients can vary from rental car customers waiting to be served in various queues depending on their membership level, to processes waiting to be executed on a computer . . . to packets belonging to various QoS classes waiting to be serviced by a router in a network.
In queuing systems, clients with higher precedence classes have higher service rates or get serviced before the clients with lower precedence classes. The privilege given to clients with higher precedence classes causes a relatively shorter waiting time for them when compared to clients with lower precedence classes. As a result, the clients in the higher precedence classes in general leave the system earlier than the clients in the lower precedence classes. To accomplish this, the queuing system often reorders the sequence of clients to service the higher precedence clients before the lower precedence clients.
In some cases, when there are no clients with higher precedence classes waiting to be serviced, the queuing system may decide to “promote” a lower precedence class client to be serviced as a high precedence class client. This may be done to keep the efficiency high in the queuing system. In other cases, when a high precedence class is over-booked with clients then the queuing system may decide to “demote” a higher precedence class client to be serviced as a low precedence class client. After the queuing system “remarks” (promotes or demotes) a client, there is an interest at least for fairness to service in order the remarked client and the other clients that originally belonged to the same precedence class. However, in the traditional queuing systems like the ones used in routers of a network shown in FIG. 1, whenever a packet (client) is promoted or demoted from one QoS class to another QoS class this may result in packet reordering either in the same node where the remark occurred or in a downstream node due to the placement of packets in different queues which observe different latencies. The reordering of packets is not desirable for reasons described below with respect to FIG. 1.
Referring to FIG. 1 (PRIOR ART), there is shown a network 100 which has a source computer 102 (user 102) that communicates with a destination computer 104 (user 104) via multiple routers/nodes 106 (only 9 routers/nodes 106 shown). Each router 106 includes a queuing system 108 with a queue 110 and a scheduler 112 that stores and implements a traditional QoS method 114. An example of the operation of the traditional QoS method 114 is described next with respect to two routers 106′ and 106″. Assume three packets are received at the router 106′ in the order 1, 2, 3. The first and the third packets belong to the same flow (e.g. Transmission Control Protocol (TCP) flow) and have a ‘lower precedence’ QoS class than the second packet which belongs to another flow. As such, packets 1 and 3 are stored in a lower precedence queue than packet 2. Assume packets 2 and 3 arrive at the time when packet 1 was being transmitted to router 106″. After packet 1 is transmitted, the scheduler 112 in router 106′ schedules packet 2 to go after packet 1 since packet 2 has a higher precedence class than packet 3. Assume also that packet 3, having complied with a certain policy, was promoted by the scheduler 112 in router 106′ to a higher precedence class. In this example, the packets are transmitted in the order 1, 2, 3 to the downstream router 106″.
At the downstream router 106″, packet 1 waits in the lower precedence queue to be scheduled for transmission. Assume in this example that packet 1 finds packet 0 being transmitted so it has to wait. While packet 1 is waiting, packets 2 and 3 are received and queued in the higher precedence class. Upon completion of the transmission of packet 0, packets 2 and 3 are scheduled to go next since they are of higher precedence than packet 1. Notice that packets 1 and 3, which belong to the same flow, got reordered in the downstream router 106″. This reordering of packets 1 and 3 is not desirable.
The reordering of packets is strongly discouraged mainly due to the high complexity and high cost associated with handling per flow reordering (as described below). If reordering is not handled properly, some higher layer protocols, like TCP for example, suffer a severe performance impact since out-of-order packets indicate packet loss and therefore congestion. This problem is described in more detail in the following references the contents of which are incorporated herein:    [1] S. Bohacek, J. P. Hespanha, J. Lee, C. Lim, K. Obraczka “TCP-PR: TCP for Persistent Packet Reordering”, Proceedings of the 23rd International Conference on Distributed Computing Systems, May 2003.    [2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Whang, and W. Weiss “An architecture for differentiated services”, RFC 2475, 1998.    [3] J. Heinanen, F. Baker, W. Weiss, J. Wroclawski “Assured Forwarding PHB Group”, RFC 2597, June 1999.In fact, in some network technologies (e.g., Asynchronous Transfer Mode (ATM)), it is strictly prohibited to reorder packets or cells.
In all of these queuing systems, the reordering of clients (packets) which originally belong to the same flow or service class when they entered the system is not desired and maybe even prohibited. In systems where several stages of service are required, the aforementioned restriction implies some cost on the routers (servers) servicing the clients (packets) if they need to maintain the order. The problem becomes even more complex when clients come in batches (i.e. flows) all labeled with the same QoS or precedence class and merge with other client batches (flows) into the same QoS queue. Accordingly, there is a need for a new queuing system and method for queuing clients (packets) in a manner that overcomes the reordering problem associated with the traditional queuing system. This need and other needs are satisfied by the queuing system and method of the present invention.